package fun.ticsmyc.dataStructure;

import fun.ticsmyc.tools.TreeNode;

import java.util.Arrays;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.dataStructure
 * @date 2020-08-03 20:11
 */
public class 根据前序和中序遍历重建二叉树 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length ==0 || inorder.length ==0){
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);

        int rootIndex =0;
        for(int i=0; i<inorder.length; ++i){
            if(inorder[i] == root.val){
                rootIndex = i;
                break;
            }
        }
        root.left=buildTree(Arrays.copyOfRange(preorder,1,1+rootIndex),Arrays.copyOfRange(inorder,0,rootIndex));
        root.right = buildTree(Arrays.copyOfRange(preorder,rootIndex+1,inorder.length), Arrays.copyOfRange(inorder,rootIndex+1,inorder.length));
        return root;
    }

    /**
     * 不拷贝数组版本
     */
    public TreeNode reConstruct(int[] pre, int[] in, int preL,int preR,int iL,int iR){
        if(preL >preR || iL>iR){
            return null;
        }
        int cur = pre[preL];
        TreeNode head = new TreeNode(cur);

        int left =0; //左子树节点个数
        for(int i=iL;i<=iR;++i){
            if(in[i]==cur){
                break;
            }
            left++;
        }

        head.left=reConstruct(pre,in,preL+1,preL+left, iL,iL+left-1);
        head.right =reConstruct(pre,in,preL+left+1,preR,iL+left+1,iR);
        return head;
    }

}
